До сравнительно недавнего времени в языке C++ не было других стандартных средств программирования, кроме старой библиотеки стандартных функций С, которая совершенно не использовала мощных нововведений, таких, как классы, шаблоны, inline-функции и исключения. Библиотека стандартных шаблонов (Standard Template Library), разработанная в HP Laboratories, явилась в свое время весьма удачным шагом в решении проблемы стандартной библиотеки ANSI C++, в которую она теперь и входит.

Это весьма обширное собрание структур данных и алгоритмов общего назначения, которое позволяет решать самые различные задачи обработки наборов данных.

Состав библиотеки стандартных шаблонов можно разбить на две категории: алгоритмы и структуры данных. Из последних можно выделить стандартные строки, поскольку они реализованы совершенно независимо от остальных элементов библиотеки. Строки мы будем обсуждать отдельно и подробнее, чем все остальное.

Состав библиотеки

Если более конкретно рассмотреть состав библиотеки стандартных шаблонов (исключив пока из рассмотрения строки), то в ней можно выделить следующие компоненты:

Вместе с STL в C++Builder предусмотрены различные дополнительные средства, например, класс комплексных чисел и средства обработки ошибок.

Заголовочные файлы

Стандартная библиотека C++ вводит новый стиль спецификации заголовочных файлов. Расширение .h опускается. Например, для подключения библиотеки алгоритмов нужно написать

#include <algorithm>

Компилятор автоматически укорачивает имя до восьми символов, добавляет .h и читает файл algorith.h из каталога $(BCB)\Include. На уровне исходного кода программы C++ получаются более мобильными, не привязанными к конкретной системе именования файлов.

Следующая таблица перечисляет стандартные заголовки STL с краткими описаниями контейнерных классов, которые они содержат.

Итераторы

Итераторы, как было замечено выше, являются центральным механизмом, обеспечивающим работу с данными контейнеров. Они являются аналогом указателей и делают возможным циклический перебор всех элементов контейнера. Существуют разные виды итераторов, поскольку различные алгоритмы по-разному обращаются к данным. Каждый класс контейнера может порождать итераторы, необходимые для работы адекватных ему алгоритмов.

Подобно указателю, итератор может ссылаться на единственный элемент данных; пара итераторов может задавать определенный диапазон контейнера; итератор может иметь т. н. запредельное значение, аналогичное NULL и означающее, что его нельзя разыменовывать.

Основными операциями над итераторами- являются, как и в случае указателей, разыменование и инкремент. Если итератор i после конечного ряда приращений может стать равным итератору j, то говорят, что итератор j достижим из i. Если к итератору, достигшему верхней границы диапазона, применить операцию инкремента, он примет запредельное значение.

Сделав такие предварительные замечания, мы перейдем теперь к конкретному изучению итераторов библиотеки стандартных шаблонов.

Существует пять основных форм итераторов:

Итераторы, стоящие в этом списке ниже, выводятся из тех, что находятся выше. Это едва ли не единственный пример классовой иерархии в 8TL.

В следующей таблице показано, какими контейнерами стандартной библиотеки генерируются те ли иные итераторы.

Чтобы продемонстрировать, как применяются итераторы, мы рассмотрим простейший вид итератора — обычный указатель. Следующая программа вызывает стандартный алгоритм find() для поиска значения в обычном массиве.

#include <algorithm>

#include <iostream>

using namespace std;

#define SIZE 50 int iArr[SIZE] ;

int main() {

iArr[30] = 33;

int *ip = find(iArr, iArr + SIZE, 33);

if (ip != iArr + SIZE)

cout<< "Value "<< *ip<< " found at position "<< (ip - iArr)<< endl;

else

cout << "Value not found."<< endl;

return 0;

}

Прежде всего обратите внимание, что программа, применяющая стандартную библиотеку C++, должна специфицировать директивой using namespace пространство имен std.

В примере объявляется “контейнер” — обычный массив длиной в 50 элементов, одному из его элементов присваивается значение 33 и вызывается алгоритм find () для поиска этого значения.

Алгоритму find () передаются три аргумента. Два из них — итераторы, задающие диапазон поиска. Первый из них в данном случае указывает на начальный элемент массива, второй имеет запредельное значение iArr + SIZE, т. е. смещен на один элемент за верхнюю границу массива. Третий аргумент задает искомое значение.

Если find () находит его в заданном диапазоне, алгоритм возвращает соответствующий ему итератор; если нет, возвращается запредельное значение.

Итераторы, генерируемые классами контейнеров, используются точно таким же образом, как указатели в показанном выше примере, но для получения граничных значений итератора вь1зываются обычно функции вроде begin () или end () конкретного контейнерного объекта. Вот совершенно аналогичный предыдущему пример для контейнера-вектора:

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

#define SIZE 50 vector<int> iVect(SIZE);

int main() {

iVect[30] = 33;

vector<int>::iterator ii =

find (iVect. begin (), iVect.endO, 33);

if (ii != iVect.endO)

cout << "Value "<< *ii<< " found at position "

<< distance(iVect.begin(), ii) << endl;

else

cout << "Value not found." <<end1;

return 0;

Объявляемый в программе контейнер имеет тип vector<int>, а итератор — тип vector<int>: : iterator. Каждый стандартный контейнер объявляет свой собственный вложенный класс iterator.

Далее мы вкратце рассмотрим различные формы итераторов.

Простейший из итераторов — входной. Он может перемещаться по контейнеру только в поступательном направлении и допускает только чтение данных. Первые два параметра алгоритма find (), например, должны быть входными итераторами. Выходной итератор отличается от входного правом доступа. Он допускает только запись данных в контейнер.

К обеим этим формам итераторов можно применять, по меньшей мере, операцию неравенства (!=), разыменования (*) и инкремента (++).

Ниже показан пример копирования массива в вектор при посредстве выходного итератора и алгоритма copy (). Его последним параметром может быть любой выходной итератор. На самом деле тот же итератор здесь используется и как входной — в операторе вывода.

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

double dArr[10] =

{1.0, 1.1, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9};

vector<double> dVect(lO);

int main()

{

vector<double>::iterator oi = dVect.begin ();

copy(dArr, dArr + 10, oi);

while (oi != dVect.endO) {

cout << *oi << endl;

oi++;

} return 0;

}

Например, ниже показано, как можно применить выходной итератор для вывода на экран содержимого контейнера.

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

int main( ) {

vector<int> iVect(lO);

for (int i=0; i<10; i++) iVect[i] = i;

cout<< "The vector contents are: { ";

copy(iVect.begin (),

iVect.endf), ostream_iterator<int>(cout, " "));

cout << "}." << endl;

return 0;

}

Поступательный итератор допускает как чтение, так и запись в контейнер. Однако, как и в случае двух предыдущих, возможен только инкремент, но не декремент итератора. Поступательные итераторы могут использоваться, например, в алгоритме replace (), который определяется так:

template <class Forwardlterator, class T>

void replace(Forwardlterator first,

Forwardlterator last,

const T &old_value,

const T &new_value);

Этот алгоритм заменяет все значения old_value, содержащиеся в контейнере, на new_value.

Двунаправленные итераторы допускают чтение и запись данных и к ним можно применять операции как инкремента, так и декремента. Такие итераторы могут быть, например, аргументами алгоритма reverse () , который меняет порядок элементов контейнера на обратный:

template <class Bidirectioriallterator>

void reverse(Bidirectionallterator first,Bidirectionallterator.last);

Такой алгоритм может быть полезен, если, скажем, из контейнера, уже сортированного в восходящем порядке, вы хотите получить контейнер с нисходящей сортировкой.

Эти итераторы являются наиболее универсальными с точки зрения возможностей доступа. Их можно использовать для произвольного чтения и записи данных контейнера. (Обычные указатели принадлежат, кстати, к этому виду итераторов.) Такие итераторы участвуют в алгоритмах сортировки, входящих в стандартную библиотеку.

Алгоритм random_shuffle, также требующий итераторов произвольного доступа, случайным образом переставляет значения элементов в указанном диапазоне контейнера:

template <class RandomAccessIterator>

void random shuffle(RandomAccessIterator first, RandomAccessIterator last);

#include <algorithm>

#include <list>

#include <iostream>

#pragma hdrstop

#include <condefs.h>

using namespace.std;

int iArr[5] = (1, 2, 3, 4, 5);

//

// Функция вывода содержимого списка.

//

void Display(list<int> &1, const char *label)

(

cout << label<< ": { ";

copy (1 .begin (), 1.end(),

ostream_iterator<int>(cout, " "));

cout << "}" << endl;

}

int main(void) {

list<int> iLst; // Создание объекта списка.

// Копирование массива в список в обратном порядке:

copy(iArr, iArr + 5, front_inserter(iLst));

Display(iLst, "Before insertion");

// Поиск значения З:

list<int>::iterator i = find(iLst.begin(),

iLst.end(), 3) ;

// Вставка массива в список:

copy(iArr, iArr + 5, inserter(iLst, i));

Display(iLst, "After insertion ");

cin.ignore ();

return 0;

}

Имеются две функции, которые могут оказаться полезными при работе с итераторами. Это advance () и distance (.) .

Функция advance () выполняет инкремент или декремент итератора указанное число раз. Ей передается итератор и число, определяющее число повторений инкремента или декремента (при отрицательном аргументе). Допустим, вам требуется найти некоторый элемент списка и установить итератор на несколько позиций за ним. Вы можете написать:

С функцией distance () вы уже встречались в примере параграфа “Итераторы контейнеров”, где с ее помощью выяснялась позиция итератора по отношению к началу вектора. Эта функция определяет количество инкрементов, которые нужно выполнить для перехода от одного итератора к другому. Она перегружена:

template <class Forwardlterator> iterator_traits<Forward!terator>::

difference_type distance(Forwardlterator first, Forwardlterator last) ;

template <class Forwardlterator, class Distance>

void distance(Forwardlterator first,

Forwardlterator last. Distance &n) ;

В упомянутом примере функция применялась в своей первой, несколько пугающей, форме, но на деле она проще второй, устаревшей. Она возвращает расстояние между итераторами как свое значение. Вторая форма функции передает расстояние в третьем параметре. Функция аккумулирует значение в этом параметре, поэтому его требуется перед вызовом инициализировать:

int d = 0;

distance (iLst, i, d);

Функции и функциональные объекты

Некоторые алгоритмы стандартной библиотеки C++ требуют функций в качестве параметров. Простейший пример — алгоритм for each (), который вызывает переданную ему функцию для каждого элемента контейнера. В этом разделе мы рассмотрим вопросы, связанные с функциональными параметрами алгоритмов.

Иногда нужно выполнить какое-то действие для каждого элемента контейнера. Упомянутый выше алгоритм for_each() позволяет сделать именно это. Функция, выполняющая необходимое действие для отдельного элемента, передается как третий аргумент алгоритма. Первые два задают диапазон. Вот пример:

void Square(int arg) { return arg * arg; }

int main() {

vector<int> iVect;

for_each(iVect.begin (), iVect.end(), Square);

}

template <class Inputlteratorl, class Inputlterator2,

class Outputlterator, class Binary0peration>_

Outputlterator transform(Inputlteratorl firsti,

Inputlteratorl lasti,

Inputlterator2 first2,

Outputlterator result,

BinaryOperation binary_func);

Первые два параметра задают диапазон первого контейнера. Параметр first2 указывает начало второго контейнера. Контейнер, куда будет записан результат, начинается с result. Последний параметр — указатель на двухместную функцию преобразования.

Особо можно выделить функции- предикаты. Предикат — это функция, возвращающая булево значение. Они используются с алгоритмами типа find_if () , который находит в указанном диапазоне значение, для которого предикат истинен:

template <class Inputlterator, class Predicate>

Inputlterator find if(Inputlterator first,

Inputlterator last,

Predicate pred);

Функциональный объект — это представитель класса, в котором определена операция вызова (скобки). Существуют различные ситуации, когда желательно передавать алгоритмам не функции, а функциональные объекты. Иногда это позволяет применить готовый функциональный объект стандартной библиотеки вместо новой функции; иногда — улучшить производительность благодаря генерированию встроенного кода. Кроме того, операция вызова может иметь доступ к информации, которая хранится в объекте — функциональный объект, в отличие от функции, обладает “памятью”.

В библиотеке шаблонов имеется ряд стандартных функциональных объектов, предназначенных для передачи алгоритмам в качестве параметра, задающего конкретную операцию. Вот они:

Например, вызов алгоритма

transform(vec.begin(), vec.endf), vec.begin(),

negate<int> ());

Типичным примером функциональнь1х объектов, сохраняющих свое состояние, являются различные генераторы, как, например, генератор случайных чисел.

Вот программа, в которой реализуется совсем простой функциональный объект — генератор чисел Фибоначчи:

//

#include <iostream>

#include <algorithm>

#include <vector>

#pragma hdrstop #include <condefs.h>

using namespace std;

int iCur, iNext;

public:

Fibo() { iNext = iCur =1; } // Инициализация состояния.

int operator ()() { // Операция вызова; возвращает

int temp = iCur; // следующий член ряда.

iCur = iNext; iNext = iCur + temp;

return temp;

} };

int main () {

//

// Сначала проверим вручную, как работает класс.

// Fibo fObj ;

cout << "Generated sequence of 16 numbers:" << endl;

for (int i=0; i<15; i++) cout << fObj () << ", ";

cout << f0bj() “ endl;

//

// Теперь генерируем вектор с помощью

// стандартного алгоритма.

//

vector<int> iVec(16);

generate (iVec .begin (), iVec.end(), Fibo());

cout << endl<< "Vector initialized by generate () algorithm:"<< endl;

copy (iVec .begin (), iVec.end(),ostream_iterator<int> (cout, " "));

return 0;

}

Программа выводит:

Generated sequence of 16 numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

Vector initialized by generate() algorithm:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

Связка создает из двухместного функционального объекта одноместный функциональный объект, фиксируя значение одного из аргументов. В библиотеке шаблонов имеется два объекта-связки, bindlst и bind2nd. Они предназначены для фиксации соответственно первого или второго аргумента.

int count = 0;

count_if (aList .begin ()., alist.end(),

bind2nd(greater<int>(), 10), count);

cout<< "Number of elements greater than 10 = " << count<< endl;

Негатор создает из функционального объекта другой объект с прямо противоположным действием, т. е. служит выражением отрицания. В библиотеке есть два негатора, noti и not2, применяемые соответственно к одноместным и двухместным функциональным объектам. Например,

noti(bind2nd(greater<int>(), 10))

означает “не больше 10”. Конечно, такое отношение можно записать и без негатора (имеется функциональный объект less_equal), но все равно негаторы часто оказываются полезны.

В стандартной библиотеке имеется десять шаблонов классов, реализующих различные структуры данных. Их перечень уже приводился в таблице 10.1. Каждый контейнер имеет свой тип iterator, через представители которого вы получаете доступ к данным. Благодаря тому, что контейнеры — это шаблоны, они обладают чрезвычайной общностью. В них можно хранить объекты, указатели на них и даже другие контейнеры, создавая, таким образом, многоуровневые структуры данных.

Есть некоторые основные принципы работы контейнеров, о которых всегда следует помнить. Среди них можно сформулировать следующие:

• В За запись объекта в контейнер отвечает конструктор копии объекта. При копировании одного контейнера в другой может быть важна перегруженная операция присваивания.
• Контейнеры сами автоматически выделяют и освобождают память по мере надобности.
• Когда программа уничтожает контейнер, она первым делом вызывает деструкторы для всех содержащихся в нем объектов. (Это не касается случая, когда в контейнере хранятся не объекты, а указатели на них.)

Векторы

Вектор — это своего рода массив с “интеллектом”, помнящий свой размер и поддерживающий свою целостность. Они, среди прочих контейнеров, отличаются эффективностью доступа к элементам. К недостаткам следует отнести сложность вставки элементов в середину вектора, поскольку при этом приходится перемещать часть его содержимого.

Объявления векторов могут выглядеть примерно так:

#include <vector>

vector<int> vint;

vector<double> vdouble (100);

vector<string> vstr(10);

vector<MyClass> myvect(20);

Короче говоря, вы можете создать либо пустой вектор, либо вектор указанного размера. Кроме размера, можно указать также начальное значение, которое будет присвоено всем элементам:

vector<int> vint1(24, -1);

Можно объявить вектор из объектов своего собственного класса. Следует при этом иметь в виду, что любой структурный тип должен иметь:

• конструктор по умолчанию
• конструктор копии
• деструктор
• операцию взятия адреса
• операцию присваивания.

Естественно, потребуются еще какие-то механизмы присваивания и извлечения значений элементов данных создаваемого объекта и т. п. Но это вопрос внешний по отношению к функционированию контейнера.

Если вы хотите выполнять поиск или сортировку, потребуются операции равенства (==) и “меньше” (<).

Скелет класса, пригодного для помещения в вектор, может иметь такой вид:

class Coord {

int x, у;

public:

Coord() : x(0), у(0) {}

void get(int &_x, int &_y) { _x = x, _y = y; ) };

Для доступа к данным вектора применяется индексация:

vstr[3] = "Third value: ";

vdouble[10] = 3.3333333333;

cout<< vstr[l]<< vdouble[10] << endl;

Можно конструировать вектор с помощью итераторов, например:

int iArr[16] ;

vector<int> iVectl(iArr, iArr + 16);

vector<int> iVect2(iVect!.begin(), iVect!.end());

(Для обычного массива, как мы уже говорили, итератором является простой указатель. Второй из векторов конструируется из первого спецификацией его начального и конечного итераторов.)

Вектор характеризуется своим размером и вместимостью. Размер — это число элементов, хранящихся в векторе в настоящий момент. Вместимость показывает предел увеличения размера вектора без дополнительного выделения памяти.

Размер и вместимость вектора можно получить с помощью его методов size() и capacity():

cout <<"Size: "<< vdouble.size ()<<"Capacity: " << vdouble .capacity () <<end1;

Есть еще функция max_size(), которая возвращает верхний предел размера и вместимости, определяемый обычно размером наибольшего доступного блока памяти.

Функция resize () позволяет изменить размер массива. Функция is_empty () возвращает true, если вектор пуст (размер равен 0). Вместимость вектора можно изменить его функцией reserve (). Заблаговременное резервирование позволяет избежать частых автоматических выделений памяти:

vdouble.reserve (1000);

Функция clear () удаляет все элементы вектора.

Функция assign () присваивает указанное значение первым n элементам:

vdouble.assign (100, 1.0);

Альтернативная форма функции позволяет присвоить элементам значения из диапазона другого контейнера:

void assign (Input-Iterator first, Inputlterator last);

Функции front() и back () возвращают значения соответственно первого и последнего элементов вектора.

Наиболее часто используемыми функциями векторов являются, вероятно, erase () и insert (). Они служат для удаления и вставки элементов. При удалении элемента (или нескольких элементов) из вектора все последующие сдвигаются к началу. Эти функции перегружены; мы приводим только две формы insert ():

iterator erase (iterator position) ;

iterator erase (iterator first, iterator last) ;

iterator insert(iterator pos, const T& x);

void insert(iterator pos,

Inputlterator first, Inputlterator last) ;

Эти функции позволяют соответственно удалить элемент, удалить диапазон, вставить элемент и вставить диапазон элементов из другого контейнера.

С помощью функций push_back () и pop_back () вектор можно использовать как стек. Первая из них вставляет элемент в конец вектора, вторая — удаляет конечный элемент (она не возвращает его значение).

Вот небольшая иллюстрация:

#include <iostream>

#include <vector>

#pragma hdrstop

#include <condefs.h>

using namespace std;

//

// Вспомогательная функция для вывода содержимого контейнера

//

template<class T> void Display(const Т &с) {

cout<< "( " ;

copy(с.begin (), c.end(),

ostream_iterator<T::value_type> (cout, " "));

cout << "} Size: " << c.size() << endl;

}

int main ()

(

int iarr[5] = (1, 2, 3, 4, 5);

vector<int> vintl(iarr, iarr + 5);

cout << "Initial vector : ";

Display(vinti);

vector<int>::iterator p =

find(vinti.begin (), vintl.end(), 3);

vinti.erase (p);

cout << "After erasing 3: ";

Display(vinti);

vinti.insert (p, iarr, iarr + 3);

cout << "After insertion: ";

Display(vinti);

cout << "Pop and push : ";

vinti.pop_back();

Display(vinti);

vinti.push back(33);

cout << " Display(vinti);

vinti.pop_back ();

return 0;

}

Программа выводит:

Initial vector : {12345} Size: 5

After erasing 3: {1245} Size: 4

After insertion: {1212345} Size: 7

Pop and push : {121234} Size: 6

{ 1 2 1 2 3 4 33 } Size: 7

Полный список функций-элементов вектора вы можете найти в оперативной справке C++Builder'a.

Списки

Списки — двусвязные линейные структуры данных, т. е. каждый элемент имеет два указателя для ссылки на два других элемента. Списки занимают ровно столько памяти, сколько необходимо для хранения наличных элементов. Вставка и удаление из списка очень эффективны. Слабым местом списка является доступ к элементам. Прямой доступ, как в векторах, невозможен. Для поиска нужного элемента приходится двигаться по списку, начиная с самого начала.

Существуют различные способы конструирования списков.

#include <list>

list<int>ilist;

list<double>dlist(20, 1.0);

list<MyType>mtlist(10) ;

Эти объявления имеют тот же смысл, что и соответствующие объявления для векторов. Так же как и вектор, список можно конструировать, инициализировав содержимым другого контейнера:

int iarr[5] = {1, 2, 3, 4, 5};

…

list<int> linti(iarr, iarr + 5);

В списке можно хранить любой тип данных, при условии, что он поддерживает те функции-элементы (конструкторы и проч.), о которых говорилось выше при обсуждении векторов.

Поскольку список занимает ровно столько памяти, сколько необходимо, для него не имеет смысла понятие вместимости. Поэтому у списков нет функций capacity () и reserve (). Невозможно и обращение к элементам по индексу.

В остальном над списками можно производить все те операции, что описывались в предыдущем параграфе о векторах. Но следует упомянуть о некоторых дополнительных возможностях списков.

Помимо известных вам уже методов push back() и pop back (), имеются функции push_front () и pop_front () для добавления или удаления элемента в начале списка.

Функция remove () удаляет из списка все элементы с указанным значением.

Функция unique () удаляет все повторяющиеся элементы (стоящие;

подряд, поэтому функцию имеет смысл применять только на сортированных списках), оставляя только первое вхождение элемента с данным значением.

Функция reverse () обращает порядок элементов в списке.

Функция sort () (без аргумента) производит сортировку списка в соответствии с операцией “меньше”, т. е. в восходящем порядке. Можно задать в качестве аргумента функциональный объект, реализующий отношение, в соответствии с которым нужно сортировать список:

#intlude <functional> linti.sort(greater_equal<int>());

Описанные функции частично иллюстрирует следующая программа.

#include <iostream>

#include <list>

#pragma hdrstop

#include <condefs.h>

using namespace std;

//

// Операция передачи списка в поток.

//

template<class T>

ostream &operator“(ostream &os, const list<T> &c)

{

cout << "{ ";

copy (c. begin (), c.end(),

ostream_iterator<T> (os, " "));

os << "} Size: " “ c.size();

return os;

}

int main() {

int iarrl[5] = {5, 7, 3, 1, 9};

list<int> lintl(iarr1, iarr1 + 5);

cout<< "Initial list : "<< linti << endl;

linti.sort (); // Сортировка.

cout << "After sort : "<< lint1 << end1;

int iarr2[6] = {6, 2, 4, 8, 2, 6};

list<int> lint2(iarr2, iarr2 + 6);

cout << "Second list : " << lint2 << end1;

lint2.sort () ;

lint2.unique(); // Удаление повторов.

cout<< "Sorted unique: " << lint2 “ endl;

linti.merge(lint2); // Слияние.

cout <<"After merge : " << lint1 “ end1;

linti.reverse (); // Обращение порядка.

cout << "After reverse: "<< lint1 << end1;

return 0;

}

Программа выводит:

Очереди deque

Контейнеры deque (формально это сокращение означает “двусторонняя очередь”) комбинируют в себе свойства списков и векторов. Они допускают прямой доступ к элементам, но эффективно работают при вставках и удалениях.

У deque имеется операция индексации и отсутствуют функции, связанные с сортировкой, так как эти контейнеры могут работать со стандартными сортировками. В остальном они похожи на списки.

Множества и мультимножества

Множества — это наборы уникальных значений; мультимножества допускают повторяющиеся значения. В остальном они совершенно идентичны, так что в дальнейшем я буду говорить просто о “множествах”.

Множество представляет собой ассоциативный контейнер с быстрым доступам к значениям элементов. Значения элементов в множестве принято называть ключами. Программа может быстро определить, находится ли данный ключ в множестве.

Элементы множества всегда сортированы. Поэтому поиск нужного ключа очень прост и эффективен.

Что касается последовательных операций и прямого доступа, то тут множества далеки от совершенства. Набор функций-элементов у множеств невелик по сравнению с другими контейнерами.

Объявляются множества несколько сложнее, чем рассмотренные до сих пор контейнеры, так как при этом необходимо указать функциональный объект, который будет использоваться при упорядочении элементов:

set<double, less<double> > dset;

Удобно переименовать представитель шаблона:

typedef set<double, less<double> > set_type;

set type dset;

Множество, как и другие контейнеры, можно создать из диапазона элементов другого контейнера:

double darr[6] = (1.0, 2.0, 2.5, 4.5, 3.5, 2.5};

set_type dset(darr, darr + 6) ;

В каком бы порядке ни следовали элементы в исходном контейнере, в множестве они окажутся сортированными.

Как я сказал, функций у множеств сравнительно немного. Функции insert () и erase () имеют дополнительную форму с одним параметром, специфицирующим ключ, который нужно добавить или удалить из множества:

dset.insert (3.14);

dset.erase(3.5);

Функции lower bound () и upper bound () возвращают соответственно итератор элемента, который больше или равен, и элемента, который больше указанного ключевого значения. Пример использования этих функций показан в приведенной ниже программе.

Функция count () возвращает 'число вхождений в множество указанного ключа. В set функция может возвращать только 0 или 1. Вызов этой функции — простейший способ определить, входит ли ключ в множество.

Следующая программа иллюстрирует эти функции множеств.

#include <iostream>

#include <set>

#pragma hdrstop

#include <condefs.h>

using namespace std;

// Дать имя типу множества;

typedef multiset<double, less<double> > set_type;

//

// Операция передачи множества в поток.

//

ostream &operator“(ostream Sos, const set_type &c)

(

cout<< "{ ";

copy(c.begin (), c.end(),

ostream_iterator<set_type::value_type>(os, " "));

os << "} Size: "<< c.sizeO;

return os;

}

int main() {

set type dset;

cout << "Inserting... ";

for (int i=8; i>0; i--) { // Ввести элементы

dset.insert (i); //в множество.

cout << i << " ";

} cout<< end1;

cout.setf(ios::fixed);

cout.precision (1) ;

cout << "Initial set : " << dset<< end1;

dset.erase (2.0); // Удалить 2.0,если есть.

cout << "2.0 erased :" << dset<< endl;

dset.insert(4); // Добавить лишние четверки.

dset.insert (4); //

cout << "4's inserted : " << dset << endl;

cout<< "Count of 4.0 :"<< dset.count (4.0)<<endl;

// Сосчитать их.

set type::iterator pi =dset.lower_bound(2.5),

p2 =dset.upper bound(6.5);

dset.erase (pi, p2); // Найти диапазон значений

// и удалить его.

cout << "Erase 2.5-6.5: " << dset<< end1;

return 0;

}

Программа выводит:

Inserting. ..87654321

Initial set : ( 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 } Size: 8

2.0 erased : {1.0 3.0 4.0 5.0 6.0 7.0 8.0 ) Size: 7

4's inserted : { 1.0 3.0 4.0 4.0 4.0 5.0 6.0 7.0 8.0 }Size: 9

Count of 4.0 : 3

Erase 2.5-6.5: { 1.0 7.0 8.0 } Size: 3

Битовые множества

Битовое множество представляет собой контейнер, в котором могут храниться битовые последовательности фиксированной длины. Можно сказать, что оно служит представлением подмножеств фиксированного множества (в математическом смысле), каждому элементу которого соответствует один бит в определенной позиции. Единичный бит означает, что элемент принадлежит подмножеству, нулевой — что он не входит в данное подмножество. Подобным образом организованы множества языка Pascal.

Биты в bitset плотно упакованы, так что информация хранится очень экономно. Однако минимальный физический размер bitset равен 4 байтам — размеру int.

При создании битового множества указывается его размер (как аргумент шаблона). Можно инициализировать bitset строкой, состоящей из нулей и единиц:

bitset<32> bset1;

bitset<8> bset2(string ( "01011011"));

У класса bitset нет итераторов, и обращение к его элементам осуществляется по индексу.

Функции set () и reset () служат соответственно для установки и сброса битов множества. При указании индекса в качестве аргумента функция устанавливает/сбрасывает соответствующий бит; при вызове функции без аргумента устанавливаются/сбрасываются все биты множества.

Функция flip () инвертирует состояние указанного бита или всех битов множества.

Вот небольшой пример, иллюстрирующий возможности битовых множеств:

#include <iostream>

#include <bitset>

#pragma hdrstop

#include <condefs.h>

using namespace std;

int main() {

bitset<8> bsetl, bset3;

bitset<8> bset2(string ("01011011"));

bsetl.set (0);

bsetl [7] = 1;

cout<< "First bitset : "<< 'bsetl<< endl;

cout << "Second bitset: " << bset2 << endl;

bsetl.flip();

cout<< "Flip first : " << bsetl << endl;

bset3 = bsetl ^ bset2;

cout << "First^second : " << bset3 << end1;

bset3 <<= 4;

cout << "Shifted by 4:" << bset3 << end1;

return 0;

}

Этот код выводит:

First bitset : 10000001

Second bitset: 01011011

Flip first : 01111110

First^second : 00100101

Shifted by 4 : 01010000

Карты и мультикарты

Карты являются ассоциативными контейнерами и очень похожи на множества за исключением того, что в картах с ключами можно связать объекты произвольного типа. Ключ, таким образом, может служить своего рода индексом, по которому можно получить доступ к ассоциированному объекту. Соответственно, на картах определена операция индексации.

Ключевые значения в картах должны быть уникальны, в мультикартах они могут повторяться. Данные хранятся сортированными по ключевым значениям.

В общем, работа с картами практически ничем не отличается от работы с множествами. Только объявление карты выглядит несколько по-другому, поскольку в нем нужно указать дополнительно тип ассоциированных объектов.

В объявлении карты (мультикарты) требуется указать три аргумента шаблона: тип ключа, тип ассоциированного значения и класс функционального объекта, которым будет определяться способ упорядочения ключей. Обычно для простоты типу карты присваивается новое имя:

typedef map<string, double, less<string> > map_type;

Ключи такого контейнера будут строками, а ассоциированные объекты — значениями типа double. Сортирована карта будет в соответствии с алфавитным порядком ключей.

Кроме того, иногда бывает удобно объявить имя для типа элемента карты (т. е. по сути структуры, состоящей из ключа и ассоциированного типа объекта; подобные типы определяются с помощью шаблона pair<Tl, Т2>):

typedef map type::value_type val_type;

Обычно создается пустая карта, а затем в нее вводятся элементы функцией insert () . Возможно также конструирование новой карты из части уже существующей. При этом конструктору передаются, как обычно, два итератора.

Важнейшие действия, выполняемые с картами и мультикартами — это поиск и извлечение данных по заданному ключу. Вообще-то карты в этом смысле практически полностью аналогичны множествам и имеют те же функции-элементы. Ниже приводится программа, демонстрирующая вариант “записной книжки” на основе мультикарты, которая может хранить несколько телефонных номеров для одного и того же имени-ключа. Нечто подобное мы уже делали в главе 8, когда говорили о перегрузке операции индексации, но индекс должен быть уникальным, а мультикарта позволяет иметь повторяющиеся ключи.

////////////////////////////////////

// Multimap.срр: Макет телефонной книжки на основе multimap.

//

#include <iostream>

#include <iomanip>

#include <map>

#pragma hdrstop using namespace std;

struct Phone {

long pn;

Phone(long n = 0): pn(n) {} };

typedef multimap<string. Phone, less<string> > map_type;

typedef map type::value type val type;

typedef map_type::iterator i_type;

//

// Выводит элемент multimap (т.е. пару (string. Phone)).

//

ostreams operator“(ostream& os, const val_type& v)

{

os << setiosflags(ios::left)<< setfill('.')

<< setw(20) << v.first

<<resetiosflags(ios::left) << setfill('0')

<< setw(3) << v.second.pn / 10000 << "-"

<< setw(4)<< v.second.pn % 10000 << setfill(' ');

return os;

}

//

// Выводит "структуру" Phone.

//

ostreamS operator“(ostreamS os. Phone p)

(

os << setw(20) << "" << setfill('0')

<< setw(3) << p.pn / 10000 << "-"

<< setw(4)<< p.pn % 10000<< setfill(' ');

return os;

}

//

// Распечатка всех номеров, относящихся к одному имени.

// Возвращает итератор, ссылающийся на первую запись с

// другим именем. Обратите внимание на функцию

// equal range(), возвращающую структуру pair.

//

i_type Retrieve(ostreams os, map_type& mp, string name)

{

pair<i__type, i type>

r = mp.equal_range(name);

// Временная карта, конструированная по паре итераторов:

map_type b(r.first, r.second);

if (b.empty())

cout << "*** No such name! ***" << endl;

else {

i type p = b. begin ();

while (p != b.end())

os << (p++)->second << endi; // Для остальных

// только номер.

} return r.second;

}

//

// Распечатка всей карты.

//

void Printout'(ostream& os, map_type& mp, i_type from)

{

while (from != mp.endO) // Если не пустая,

// распечатать

from = Retrieve (os, mp, from->first);

// все номера

// первого ключа

//и перейти к

// следующему.

os << "*** End of the book ***" << endl;

}

ostreamS operator<<(ostreamb os, map_type& v) {

Printout (os, v, v.begin ());

return os;

}

int main() {

map type book;

// Попробуем распечатать пустую карту...

cout << "Contents of a new book:" << end1;

cout << book << endl;

book.insert(val_type("Petrov", 1653318));

book.insert(val_type("Ivanov", 2640535));

book.insert(val_type("Sidorov", 2340711));

book.insert(val_type("Ivanov", 4720415));

book.insert(val_type("Petrov", 1770212));

book.insert(val_type("Pavlov", 5551703));

book.insert(val_type("Ivanov", 4722306)) ;

// Распечатка.

cout << "Contents of the phone book:" << endl;

cout << book << end1;

// Поиск отдельных имен.

cout << "Searching Petrov... " << endl;

Retrieve(cout, book, "Petrov");

cout << "Searching Kozlov... " << end1;

Retrieve(cout, book, "Kozlov");

return 0;

}

Поиск нужного имени в этой программе выполняется функцией equal_range (), которая возвращает пару итераторов (структуру pair), ссылающихся на начало и конец диапазона с одним и тем же заданным ключом (если он присутствует).

Результат запуска программы показан на рис. 11.2.

Стеки

Стек — очень простая структура данных. В STL можно организовать три разновидности стеков: на основе вектора, на основе списка и на основе deque. Функционально они не отличаются друг от друга.

При конструировании стека нужно указать не только тип хранящихся в нем объектов, но и тип контейнера, на основе которого стек будет реализован:

#include <stack>

#include <vector>

stack<int, vector<int> > iStack;

Функция push () помещает указанное значение на вершину стека;

функция pop () удаляет из стека верхнее значение. Получить значение с вершины стека можно функцией top ():

for (int i=0; i<10; i++) iStack.push(i) ;

while (!iStack.empty()) {

cout<< iStack.topO << endl;

iStack.pop();

}

Очереди

Очередь отличается от стека порядком извлечения элементов: если в стеке операция pop () удаляет самый последний из помещавшихся в него элементов, то в очереди там же операция удаляет наиболее “старый” элемент. Получить значение этого элемента можно, вызвав функцию front ().

Очередь может быть конструирована на основе либо списка, либо deque. Вот пример, аналогичный примеру со стеком из предыдущего параграфа:

#include <queue>

#include <list>

queue<int, list<int> > iQueue;

for (int i=0; i<10; i++) iQueue.push (i);

while (!iQueue.empty ()) {

cout << iQueue.front() << end1;

iQueue.pop ();

}

Приоритетные очереди

При конструировании очереди в общем случае указывается тип элементов, тип контейнера-основы и функциональный объект, определяющий приоритеты. Контейнером-основой для приоритетной очереди может быть вектор или deque.

Вот маленький пример, моделирующий составление списка неотложных дел в порядке их важности:

////////////////////////////////////////

// Priority.срр: Демонстрация приоритетной очереди.

//

#include <iostream>

#include <string>

#include <queue>

#include <deque>

#pragma hdrstop

using namespace std;

class ToDo {

int priority;

string doit;

public:

ToDo(int p = 0, string d = ""): priority(p), doit(d) {}

bool operator<(const ToDo &arg) const { return priority < arg.priority; }

friend ostream &operator<<(ostreams, const ToDo&);

};

ostream &operator<<(ostream &os, const ToDo &t) {

os << t.priority << " - " << t.doit;

return os;

}

int main() {

priority_queue<ToDo, deque<ToDo>, less<ToDo> > todo;

todo.push(ToDo(7, "Write a letter to X."));

todo.push(ToDo(4, "Buy some food for dinner."));

todo.push(ToDo(1, "Call your publisher."));

// Распечатать список в порядке срочности. while (!todo.empty()) {

cout << todo.top() << endl;

todo-pop() ;

)

return 0;

)

Программа выводит:

7 - Write a letter to X.

4 - Buy some food for dinner.

3 - Finish the program you started yesterday.

Алгоритмы стандартной библиотеки выполняют разные распространенные действия на наборах данных, представленных стандартными контейнерами. Среди этих действий можно назвать сортировку, поиск, замену и т. д. Ниже мы вкратце опишем имеющиеся в библиотеке алгоритмы, не вдаваясь в подробности и не приводя развернутых примеров. Применение стандартных алгоритмов достаточно очевидно и, как правило, не вызывает никаких затруднений.

#include <algorithm>

using namespace std;

(Не забывайте указывать пространство имен std, когда пользуетесь новой нотацией включаемых файлов!)

Некоторые алгоритмы вы уже видели (например, find ()), так что здесь мы показываем в основном те, с которыми вы еще не встречались.

Накопление

Накопление, или аккумуляция — это перебор заданного диапазона контейнера с суммированием (иди перемножением, или какой-то иной комбинацией) элементов в некоторой итоговой переменной. По умолчанию выполняется суммирование:

#include <numeric> double sum = accumulate(v.begin (), v.end(), 0.0);

Третий параметр алгоритма — начальное значение аккумулятора. При суммировании это обычно ноль. В качестве четвертого параметра можно задать функциональный объект, определяющий аккумулирующую операцию. Вот, например, как вычисляется произведение всех элементов вектора:

#include <numeric>

#include <functional>

double product = accumulate(v.begin(), v.end(),

1.0, multiplies<double> ());

Подсчет

Алгоритм count () осуществляет подсчет числа элементов контейнера с указанным значением. Алгоритм count_if() выполняет подсчет элементов, для которых выполняется условие заданного предиката:

void count(Inputlterator first, Inputlterator last,

const T& value, Size& count) ;

void count if(Inputlterator first, Inputlterator last,

Predicate p, Size& count);

Результат подсчета возвращается в четвертом параметре.

Поиск и замена

С алгоритмом поиска вы уже встречались не раз:

Inputlterator

find(Inputlterator first, Inputlterator last,

const T& value);

Inputlterator

find(Inputlterator first, Inputlterator last,

Predicate pred) ;

Вторая форма возвращает итератор первого элемента, для которого истинен указанный предикат.

Алгоритмы замены replace () и replace_if() позволяют заменять существующие значения контейнера новыми:

void replace(Forwardlterator first, Forwardlterator last,

const T& value, const T& new_value) ;

void replace_if(Forwardlterator first, Forwardlterator last,

Predicate pred, const T& new_value) ;

Удаление элементов

Удаление элементов контейнера с указанным значением выполняется алгоритмами remove () и remove_if:

Forwardlterator

remove(Forwardlterator first, Forwardlterator last,

const T& value) ;

Forwardlterator

remove if(Forwardlterator first, Forwardlterator last,

Predicate pred) ;

Необходимо заметить, что эти алгоритмы не уменьшают числа элементов в контейнере. Они только сдвигают элементы, которые должны остаться в новом наборе, к его началу, и возвращают итератор конца нового набора элементов. Чтобы действительно удалить ненужные элементы, нужно применить метод контейнера erase ():

array.erase(remove(array.first(), array.end(), value),

array.end());

Алгоритм unique () удаляет из контейнера все элементы с повторяющимися значениями, следующие друг за другом, оставляя только первый из них:

Forwardlterator remove(Forwardlterator first, Forwardlterator last);

Алгоритм возвращает итератор конца нового набора элементов.

Перестановка

Алгоритм random_shuffle () производит случайную перестановку элементов контейнера:

void random_shuffle(RandomAccessIterator first,

RandomAccessIterator last);

В качестве третьего аргумента можно указать функциональный объект с целым параметром, задающим диапазон генерируемых им случайных чисел.

Алгоритм может быть полезен не только для задач вроде тасовки колоды карт, но и для подготовки, например, тестовых наборов данных для программ сортировки и т. п.

Лексикографическое сравнение

Такое страшное название алгоритма означает всего-навсего, что он выполняет сравнение содержимого двух контейнеров, аналогичное сравнению текстовых строк. Элементы контейнеров могут быть любого типа, лишь бы для них была объявлена операция “меньше” (или какая-либо функция, задающая отношение сравнения):

bool

lexicographical_compare (Inputlteratorl first1,

Inputlteratorl last1,

Inputlterator2 first2,

Inputlterator2 last2);

bool lexicographical compare(Inputlteratorl first1,

Inputlteratorl last1,

Inputlterator2 first2,

Inputlterator2 last2,

Compare comp);

Алгоритм возвращает true, если содержимое первого контейнера меньше, чем второго.

Сортировка

С сортировкой мы уже встречались, правда, в виде функции контейнера (при изучении списков — их нельзя сортировать по-другому), а не отдельного алгоритма. Сортировка по умолчанию производится в восходящем порядке (используется операция < для сравнения элементов):

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first,

RandomAccessIterator last. Compare comp);

Под стандартными строками понимают объекты, принадлежащие шаблону basic_string, чаще всего его классам-представителям string или wstring. В повседневном .программировании применяется почти исключительно класс string.

Стандартные строки имеют ряд преимуществ перед строками “в стиле С”, т. е. строками с ограничивающим нулем, хранящимися в массивах типа char. Строки стандартной библиотеки шаблонов можно считать контейнерами, однако они реализованы совершенно отдельно от остальных контейнеров, рассматривавшихся в предыдущем разделе.

Чтобы можно было работать со стандартными строками, необходимо включить в программу заголовок string. При этом, кстати, автоматически подключается заголовок С string, h, так что вы можете при этом пользоваться стандартными функциями С для строк, ограниченных нулем.

Создание строк

Конструировать строки можно многими способами; можно создать пустую строку (конструктор по умолчанию), можно инициализировать строку литералом, присваиванием литерала или копированием, можно зарезервировать указанное число символов, инициализировав в то же время строку литералом меньшей длины, можно создать строку из стандартного контейнера (например, вектора), содержащего символы, и т. д. Ниже приводится ряд примеров конструирования строк.

string sEmpty;

string sLiteral("A string from literal.");

string sAssign = "A string by assign.";

string sCopy(sLiteral);

string sPart(sCopy, 14, 7);

string sFill(32, '#') ;

Пояснений, вероятно, требуют только два последних конструктора. Предпоследний создает строку из уже существующей, выделяя ее подстроку длиной 7 символов, начиная с индекса 14. Последний конструктор создает строку длиной 32 символа, заполняя ее символами ' # '.

Характеристики строк

Как и контейнеры, строки характеризуются своим размером и вместимостью. Вот сводка функций-элементов, позволяющих манипулировать различными характеристиками строк. Они аналогичны соответствующим функциям контейнеров:

Функции resize () и reserve () могут выбрасывать исключение length_error, если запрашиваемый размер больше максимально возможного (он обычно определяется размером наибольшего свободного блока памяти).

Ввод и вывод строк

Наиболее прост вывод строк с помощью операции <<:

string s("This is a string!");

cout << s << end1;

По форме это ничем не отличается от вывода строки С. Ввод строки вроде бы тоже выглядит очень просто:

string s;

cin >> s;

string s;

getline(cin, s, '\n');

Ограничитель ' \n ' можно было бы и не указывать, так как он принимается по умолчанию.

Операции над строками

Для стандартных строк перегружен ряд операций.

Операция присваивания позволяет присвоить стандартной строке другую строку, строку С (или литерал), отдельный символ. Все показанные ниже присваивания допустимы:

char cs[20] = "С string.";

string sOld("Source string.");

string sNew;

sNew = sOld;

sNew = cs;

sNew = "Literal string.";

sNew = c;

Перегруженная операция сложения выполняет конкатенацию строк, причем возможна как конкатенация двух строк с присвоением результата третьей строке, так и присоединение строки в конец другой строки с помощью присваивания +=:

string si("First"), s2("Second");

string s3;

s3 = si + " " + s2;

si += s2;

Строки можно индексировать. При обычной нотации индексации проверки диапазона не делается. Однако можно применить функцию at (), также возвращающую ссылку на символ строки с указанным индексом. В этом случае при выходе за текущую длину строки выбрасывается исключение out_of_range:

string s("A short string.");

try {

cout<< s.at(30) << endl;

) catch(out_of_range e) {

cout << "Range error: "<< end! << e.what() << endl;

}

Этот фрагмент кода выводит:

Range error:

position beyond end of string in function:

basic_string::at(size_t)

index: 30 is greater than max index: 15

Наконец, для стандартных строк перегружен весь набор операций отношений: равенство, неравенство, “больше”, “меньше” и т. д. Операции < и > производят лексикографическое сравнение в соответствии с алфавитным порядком.

Функции строк

Класс string (точнее, basic_string) имеет богатый набор функций, выполняющих обработку строк. Мы расскажем только о некоторых.

string si("Some String already exists."), s2;

s2.assign (si, 5, 6); // Скопирует только слово "String".

Функции assign () и append () имеют аналогичные перегруженные формы и различаются только тем, что первая полностью заменяет текущее содержимое строки новым текстом, а вторая дописывает тот же текст в конец строки. Приведем все имеющиеся формы этих функций, чтобы дать читателю представление о том, что там вообще есть (возвращаемый тип пропущен — все они возвращают basic_string&):

append (const basic strings s);

append (const. basic_string& s, size type pos, size_type npos);

append (const charT* s, size type n);

append (const charT* s);

append (size_type n, charT с );

append (Inputlterator first, Inputlterator last);

assign (const basic strings s);

assign (const basic_string& s,

size__type pos, size_type n);

assign (const charT* s, size type n);

assign (const charT* s);

assign (Inputlterator first, Inputlterator last);

Функции insert () и erase () производят соответственно вставку указанного текста в заданное место строки и удаление фрагмента строки. Третья функция, replace (), является их комбинацией: делается вставка, а затем часть старого содержимого строки удаляется.

Приведем всего один пример, простейший:

string s1 ("First string.");

string s2(" and second");

si.insert(s1.find(' '),s2);

В данном случае insert () вставляет содержимое второй строки в первую перед найденным в ней пробелом. Следующий оператор удалит только что вставленную строку:

sl.erase(sl.find(' '), 11);

Есть восемь перегруженных вариантов функции insert () и десять вариантов replace () . Для erase () , правда, имеются всего три формы. Все это при желании читатель может найти в оперативной справке С++Вuilder.

Функции семейства поиска очень разнообразны. Различные разновидности их еще и перегружены, так что общее число доходит до двух десятков. Функции семейства могут выполнять следующие операции.

Функция find () наиболее проста; она ищет первое вхождение строки, строки С или одиночного символа, начиная с указанного места, по умолчанию от начала, и возвращает позицию найденного фрагмента:

int i = s1.find("and");

Вот простейший пример подобного поиска:

string s("13:30:00 11/03/2000");

int k=0;

k=s.find_first_of(" :/",k) ;

Обычно эти функции используются для поиска разделителей или пропуска незначащих символов при синтаксическом разборе строк.

char buf[40];

string s = "abcdefghijklmnopqrstuvwxyz";

s.copy(buf 10 3);

buf[10]='\0';

Этот фрагмент копирует 10 символов из строки s в символьный буфер, начиная с 3-й позиции (т. е. с буквы d). Функция copy (), правда, не записывает в буфер конечный нуль, так что его приходится добавлять вручную.

В этой главе вы познакомились с библиотекой стандартных шаблонов, то есть с контейнерами, строками и всем, что с ними связано — итераторами, функциональными объектами и т. п. Сила стандартных контейнеров в том, что они представляют собой готовые динамические структуры данных, которые сами следят за выделением и удалением памяти под свои данные. Программисту остается только грамотно написать базовый класс для хранящихся в контейнере объектов, снабдив его необходимыми конструкторами, деструкторами и перегруженными операциями. Все остальное сделает контейнер, обеспечив поддержание корректности структуры данных в процессе работы программы.